C Mængder, kvantorer, udsagn og beviser

En mængde $A$ er en samling af forskellige objekter. Denne noget intuitive beskrivelse af en mængde er tilstrækkelig i de fleste sammenhænge, og vi vil ikke præcisere definitionen nærmere (hvilket hurtigt bliver ret kompliceret). Et objekt $a$ i en mængde $A$ kaldes også for et element i $A$ , og vi skriver i givet fald $a \in A$ . I dette tilfælde siger vi også, at $a$ tilhører $A$ . Hvis et givet objekt $b$ ikke tilhører $A$ , så skriver vi $b \notin A$ . En mængde $A$ kaldes endelig, hvis den kun indeholder endeligt mange elementer. I modsat fald kaldes $A$ for en uendelig mængde. Blandt de endelige mængder findes den tomme mængde $\emptyset$ ; altså mængden der ikke indeholder nogen objekter.

Mængder kan beskrives ved at fortælle, hvilke objekter de indeholder. F.eks. betyder

$A = \left\{ 1 , 2, 5 \right\},$ at $A$ er en mængde bestående af tallene $1$ , $2$ og $5$ . En notation af formen

$B= \left\{ 1,2,3,\ldots,271 \right\}, \tag{C.1}$ betyder, at $B$ er mængden bestående af alle heltal fra $1$ til $271$ . I (C.1) præciserer vi ikke alle elementer i $B$ , men angiver alene et mønster for, hvordan elementerne i $B$ fremkommer.

To mængder $A$ og $B$ er identiske, hvis de indeholder de samme elementer, og vi skriver i givet fald $A=B$ . Notationen $A \subseteq B$ anvendes, hvis ethvert element i $A$ også er et element i $B$ ; i givet fald kalder vi $A$ for en delmængde af $B$ . Det er derfor klart, at $A=B$ er det samme som, at både $A \subseteq B$ og $B \subseteq A$ . Mange sætninger udtaler sig om, at to givne mængder $A$ og $B$ er ens, og ofte vises sådanne udsagn ved at vise, at ethvert element i $A$ også er et element i $B$ (dvs. $A \subseteq B$ ) og vice versa (dvs. $B \subseteq A$ ).

Såfremt $C$ er en mængde, og $A$ og $B$ begge er delmængder af $C$ , så anvender vi notationen $A \cup B$ om foreningen af $A$ og $B$ ; dvs. om den delmængde af $C$ , der består af de elementer, der enten tilhører $A$ eller $B$ . Notationen $A \cap B$ betegner fællesmængden af $A$ og $B$ , og er den delmængde af elementer i $C$ , der både tilhører $A$ og $B$ . Endeligt vil vi anvende notationen $A \setminus B$ om den delmængde i $C$ , der består af de elementer, der tilhører $A$ , men som ikke tilhører $B$ . F.eks. har vi da, at hvis $C=\{ 1,2,3,4,5,6 \}$ , $A=\{ 1,2,3,4 \}$ og $B=\{2,4,6 \}$ at

$\begin{aligned} A \cup B & = \{ 1,2,3,4,6 \} \\ A \cap B & = \{ 2, 4 \} \\ A \setminus B & = \{ 1,3 \}. \end{aligned}$

I disse noter vil vi anvende betegnelsen $\mathbb{Z}$ om mængden af alle heltal; dvs.

$\mathbb{Z} = \{ \ldots, -4,-3,-2,-1,0,1,2,3,4,\ldots \},$ mens mængden af positive heltal vil blive betegnet med

$\mathbb{N} = \{1,2,3,4,\ldots \},$ og vil blive omtalt som de naturlige tal. Herudover, så anvender vi notationen $\mathbb{Q}$ om mængden af rationale tal (dvs. tal på formen $\frac{p}{q}$ , for $p,q \in \mathbb{Z}$ ). Mængden af reelle og komplekse tal vil blive betegnet med hhv. $\mathbb{R}$ og $\mathbb{C}$ .

C.1 Udsagn

Et matematisk udsagn (eller blot et udsagn) er en udtalelse, der enten er sand eller falsk. F.eks. er udtalelsen “ $1=2$ ” falsk og dermed et udsagn. Tilsvarende er udtalelsen “ $2=1+1$ ” sand og dermed også et udsagn. Derimod er udtalelsen “21 gule biler” hverken sand eller falsk og dermed ikke et matematisk udsagn. To udsagn $p$ og $q$ siges at være ækvivalente, hvis de har samme sandhedsværdi; dvs. hvis enten $p$ og $q$ begge er sande udsagn, eller begge er falske udsagn.

Quiz

Markér de felter, der indeholder et udsagn i matematisk forstand.

Alle biler er røde

$\frac{3}{4\cdot\pi^2}$

$E=m\cdot c^2$

$6 + 8^2$

Lad $x \in \mathbb{R}$ og $y \in \mathbb{N}$

Velkommen til lineær algebra

$\mathbb{R}$ er et legeme

$\mathbb{N}$ er et legeme

Ud fra to udsagn $p$ og $q$ kan vi konstruere andre udsagn. Vi skriver:

$p \wedge q$ om udsagnet der alene er sandt, hvis $p$ og $q$ begge er sande.
$p \vee q$ om udsagnet der alene er falsk, hvis $p$ og $q$ begge er falske.
$\neg p$ om udsagnet der alene er falsk, når $p$ er sandt (dvs. specielt er $\neg p$ sandt, når $p$ er falsk).
$p \Rightarrow q$ om udsagnet der alene er falsk, hvis $p$ er sand og $q$ er falsk.
$p \Leftarrow q$ om udsagnet $q \Rightarrow p$ .
$p \Leftrightarrow q$ om udsagnet der alene er sandt, hvis $p$ og $q$ er ækvivalente udsagn.

Det er en nyttig opgave at vise, at $p \Leftrightarrow q$ er sandt, netop når både $p \Rightarrow q$ og $q \Rightarrow p$ er sande. Med andre ord er følgende udsagn sandt

$(p \Leftrightarrow q) \Leftrightarrow ((p \Rightarrow q) \wedge (q \Rightarrow p)) \tag{C.2}$

En sætning udtaler sig om, hvorvidt et givet udsagn er falsk eller sandt. F.eks. skal en sætning af formen

$p \Leftrightarrow q.$

forstås som, at udsagnet $p \Leftrightarrow q$ er sandt; dvs. at $p$ og $q$ er ækvivalente udsagn. Ifølge (C.2) så kan et sådant udsagn vises ved at vise følgende to udsagn:

Hvis $p$ er sandt, så er $q$ sandt (svarende til at udsagnet $p \Rightarrow q$ er sandt).
Hvis $q$ er sandt, så er $p$ sandt (svarende til at udsagnet $q \Rightarrow p$ er sandt).

Til tider vælger man at studere sandhedsværdien af udsagnet $p \Rightarrow q$ ved at studere det kontraponerede udsagn $\neg q \Rightarrow \neg p$ . At dette er muligt skyldes, at $p \Rightarrow q$ og $\neg q \Rightarrow \neg p$ er ækvivalente udsagn; dvs. følgende udsagn er sandt

$(p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p).$ Det overlades til læseren at indse denne ækvivalens.

Quiz

I nedenstående betegner $x$ et reelt tal. Indsæt de korrekte symboler, så udsagnene bliver sande

$x^2=4$

$x=2$

$x^2=4$

$x=2$

$x=-2$

$\vee$

$\Leftrightarrow$

$\Leftarrow$

C.2 Kvantorer

I formulering af udsagn anvender vi ofte al-kvantoren $\forall$ og eksistens-kvantoren $\exists$ . Disse kvantorer er matematisk notation for hhv. “for alle” og “der eksisterer”. F.eks. udtrykker udsagnet

$\forall x \in \mathbb{R} \colon x^2 \geq 0,$ at kvadratet på alle reelle tal er positivt eller lig $0$ . Kvantorer kan også kombineres som f.eks. i

$\forall x \in \mathbb{R}, \exists y \in \mathbb{R} \colon y < x,$ der udtrykker, at der for alle reelle tal $x$ , eksisterer et reelt tal $y$ , der er mindre end $x$ . Til tider anvendes notationen $\exists !$ som betegnelse for, at “der eksisterer et entydigt”. F.eks. udtrykker

$\exists ! a \in \mathbb{N} \colon a^2 = 25,$ at der eksisterer et entydigt naturligt tal med kvadrat 25.

Quiz

Opskriv følgende sætning med kvantorer og matematiske symboler: For alle reelle tal $x$ , eksisterer der heltal $y$ og $z$ , således at $x$ er større end $y$ , og $x$ er mindre end $z$ .

$\exists x \in \mathbb{R} \forall y,z \in \mathbb{Z} : y < x < z$

$\forall x \in \mathbb{R} \exists y,z \in \mathbb{Z} \Rightarrow y < x < z$

$\exists x \in \mathbb{R}\exists y,z \in \mathbb{Z} \Rightarrow y < x < z$

$\forall x \in \mathbb{R} \exists y,z \in \mathbb{Z} : y < x < z$

$\forall x \in \mathbb{N} \forall y,z \in \mathbb{Z} : y < x < z$

$\forall x \in \mathbb{R} \Rightarrow \exists y,z \in \mathbb{Z} : z < x < y$

$\forall x \in \mathbb{R} \Rightarrow \exists y,z \in \mathbb{Z} \Leftrightarrow z < x <y$

C.3 Induktionsbeviser

Lad $A$ betegne en delmængde af de naturlige tal

$\mathbb{N} = \left\{ 1,2,3,\ldots \right\}.$ Vi beskriver nu et kriterium, der sikrer, at $A$ er lig $\mathbb{N}$ . Vi påstår, at $A$ er lig $\mathbb{N}$ blot $A$ har følgende egenskaber:

$1 \in A$ .
Hvis et element $a \in \mathbb{N}$ er indeholdt i $A$ , så vil $a+1$ også være indeholdt i $A$ .

Ideen er, at hvis $1 \in A$ (iflg. betingelse (1.)), så vil $2 \in A$ ifølge betingelse (2.). Herefter vil $3 \in A$ ifølge betingelse (2.), og så fremdeles. Denne egenskab ved $\mathbb{N}$ ligger til grund for induktionsbeviser.

I forbindelse med induktionsbeviser betragter man en samling af udsagn indekseret ved elementerne i $\mathbb{N}$ ; dvs. man har et udsagn $P_i$ for ethvert $i \in \mathbb{N}$ . Sættes

$A = \left\{i \in \mathbb{N} \mid P_i \text{ er sandt}\right\},$ så er $A$ en delmængde af $\mathbb{N}$ . At alle udsagn $P_i$ , for $i \in \mathbb{N}$ , er sande, er da ækvivalent med, at $A = \mathbb{N}$ . Det sidste udsagn kan tjekkes via ovenstående kriterium, og vi konkluderer dermed, at $P_i$ er sandt, for alle $i \in \mathbb{N}$ , såfremt:

$P_1$ er sandt.
For alle $n \in \mathbb{N}$ gælder: Hvis $P_n$ er sandt, så er $P_{n+1}$ sandt.

Udsagn (a.) omtales også som induktionsstarten, mens (b.) kaldes induktionsskridtet. Udsagnet $P_n$ kaldes induktionshypotesen. At anvende (a.) og (b.) til at vise gyldigheden af alle udsagn $P_n$ , for $n \in \mathbb{N}$ , omtales som, at $P_n$ er vist via matematisk induktion i $n$ . Pga. beskrivelsen af (b.) så vil der oftest være en forbindelse mellem de betragtede udsagn $P_1,P_2,P_3 \ldots$ .

Til tider er det nyttig at anvende en anden form for induktion, der ofte omtales som stærk induktion. Her erstattes udsagnene (a.) og (b.) med:

$P_1$ er sandt.
For alle $n \in \mathbb{N}$ gælder: Hvis $P_i$ er sandt for alle $i \leq n$ , så er $P_{n+1}$ sandt.

Det overlades til læseren at overveje, at hvis (c.) og (d.) er opfyldte, så er $P_i$ sandt for alle $i \in \mathbb{N}$ .

For alle $n \in \mathbb{N}$ lader vi $P_n$ betegne udsagnet, at

$1+2+3+ \ldots + n = \frac{n(n+1)}{2},$ er opfyldt. Vi vil nu vise, at $P_n$ er sandt for alle $n \in \mathbb{N}$ via induktion i $n$ . Induktionsstarten er ækvivalent med, at

$1=\frac{1(1+1)}{2},$ hvilket er oplagt. Antag herefter, at $n \geq 1$ , og at $P_n$ er sandt; dvs. at identiteten

$1+2+3+ \ldots + n = \frac{n(n+1)}{2}, \tag{C.3}$ er opfyldt. I induktionsskridtet skal vi da konkludere, at $P_{n+1}$ er sandt; altså at

$1+2+3+ \ldots + n +(n+1)= \frac{(n+1)(n+2)}{2}. \tag{C.4}$ Men venstresiden i (C.4) kan, jf. antagelsen (C.3), beregnes som

$\frac{n(n+1)}{2} + (n+1) = \frac{n(n+1)+ 2(n+1)}{2} = \frac{(n+1)(n+2)}{2},$ og vi konkluderer hermed, at $P_{n+1}$ er sandt hvis $P_n$ er sandt. Samlet konluderer vi, at $P_n$ er sandt for alle $n \in \mathbb{N}$ .

Udover den ovennævnte beskrivelse af matematisk induktion så eksisterer der et væld af varianter. Oftest betragter man en samling af udsagn indekseret ved en delmængde $M$ af $\mathbb{N}$ (eller $\mathbb{Z}$ ); dvs. man betragter udsagn $P_n$ for $n \in M$ . Hvis f.eks.

$M = \left\{ 2,3,4,\ldots \right\},$ så kan gyldigheden af $P_n$ , for alle $n \in M$ , tjekkes ved følgende betingelser:

$P_2$ er sandt.
For alle $n \geq 2$ gælder: Hvis $P_n$ er sandt, så er $P_{n+1}$ sandt.

Tilsvarende hvis

$M = \left\{ 2,3,4,5,6,7,8,9 \right\},$ så er $P_n$ sandt, for alle $n \in M$ , såfremt:

$P_2$ er sandt.
For alle $n \in M \setminus \left\{ 9 \right\}$ gælder: Hvis $P_n$ er sandt, så er $P_{n+1}$ sandt.